package com.congee02;

import java.util.Arrays;

public class Rob_Cache {

    public int rob(int[] nums) {

        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        int[] dp = new int[n];

        dp[n - 1] = nums[n - 1];
        dp[n - 2] = Math.max(nums[n - 1], nums[n - 2]);

        for (int i = n - 3 ; i >= 0 ; i -- ) {
            dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
        }

        return dp[0];
    }

    private int[] cache = new int[101];
    private int process(int[] nums, int index) {
        if (index < 0) {
            return 0;
        }
        if (index >= nums.length) {
            return 0;
        }
        if (cache[index] == -1) {
            cache[index] = Math.max(
                    nums[index] + process(nums, index + 2),
                    process(nums, index + 1)
            );
        }

        return cache[index];
    }

}
